########################################################

#This maze generator is based on the pseudo-code from 
#http://www.mazeworks.com/mazegen/mazetut/index.htm. Only the specific implementation
#can be accredited to Authors: James Anderson and Roger Burns

########################################################
import sys,random

class MazeCell:
    #keep track of the walls. 0 means no wall exists, 1 means a wall exist.
    #Maps to : N, E, S, W
    CellWalls=int('1111',2)
    North= int('0111',2)
    East= int('1011',2)
    South= int('1101',2)
    West= int('1110',2)
    #Variable to identify if the cell has been visited or not.
    Visited=False
    #init
    def __init__(self,bool):
        self.Visited = bool
    def SetWall(self,dir):
        if dir=="N":
            self.CellWalls= self.CellWalls&MazeCell.North
        elif dir=="E":
            self.CellWalls= self.CellWalls&MazeCell.East
        elif dir=="S":
            self.CellWalls= self.CellWalls&MazeCell.South
        elif dir=="W":
            self.CellWalls= self.CellWalls&MazeCell.West
    #
    def PrintWalls(self):
        print(MazeCell.CellWalls)

################################################################################

#instantiate size of the maze to create
def GenerateMaze(height,width):
    
    ############################################################################
    #Maze Variable - multidimensional Maze List
    
    #**NOTE: Multidimensional Arrays are not handled as per c++/java
    #Nested Lists are they way to go.
    #http://docs.python.org/faq/programming.html#how-do-i-create-a-multidimensional-list
    Maze=[MazeCell]*width
    for i in range(width):
        Maze[i]=[MazeCell]*height
    
    ############################################################################
    #Cell Variables

    #Stack to hold Cell Coordinates
    CellStack=[]
    #total number of cells
    CellsTotal = width*height
    #number of cells that have been visited
    CellsConsumed=0
    #StartingCell
    CellStart=[0,0]
    #Set N,E,S,W Variables - used to determine direction from current cell in 
    #main loop
    North=[0,1]
    East=[1,0]
    South=[0,-1]
    West=[-1,0]
    
    #Fill Maze with Cells - use height and width passed to GenerateMaze function
    for i in range(0,height):
        for j in range(0,width):
            Maze[i][j]= MazeCell(False)            
    ############################################################################
    def AppendCell(CList):
        """
        Method to Set the current coordinates in the Grid to True, append
        current coordinates to cell stack and increment cells consumed by
        main loop
        """
        Maze[CList[0]][CList[1]].Visited=True
        CellStack.append(CList)
        
        
    ############################################################################
    def TestCell(direction):
        """
        Test to see if Cell at coordinates was visited
        """
        #local variables to hold new Maze Coordinates
        x=direction[0]+CellStack[-1][0]
        y=direction[1]+CellStack[-1][1] 
        #Check for valid grid range: negative values
        if x<0 or y<0:
            #print("Invalid Range: Negative Value")
            return 0
        elif x>=width or y>=height:
            #print("Invalid Range: Outside Grid Bounds")
            return 0
        #if visited, return and do nothing (i.e. 0)
        elif Maze[x][y].Visited==True: 
            return 0
        #otherwise return Direction (which is only the offsets of the direction
        else: return direction
    
    ############################################################################
    def GetNeighbors(Cell):
        """
        Method to return a list of the neighbors of the MazeCell
        @return: List containing Cell Coordinates in format: List[x,y]
        """
        Neighbors=[]
        #test 4 sides of cell
        CNorth=TestCell(North)
        CEast=TestCell(East)
        CSouth=TestCell(South)
        CWest=TestCell(West)
        if CNorth:Neighbors.append(CNorth)
        if CEast:Neighbors.append(CEast)
        if CSouth:Neighbors.append(CSouth)
        if CWest:Neighbors.append(CWest)
        #print(Neighbors)
        return Neighbors
    ############################################################################
    def SetWalls(x,y):
        CurrentCell=Maze[CellStack[-1][0]][CellStack[-1][1]]
        if y == 1:
            #remove north wall
            CurrentCell.SetWall("N")
        elif x == 1:
            #remove east wall
            CurrentCell.SetWall("E")
        elif y == -1:
            #remove south wall
            CurrentCell.SetWall("S")
        elif x == -1:
            #remove west wall
            CurrentCell.SetWall("W")
        return
    ############################################################################
    def PrintMaze():
        #Print Maze Walls
        print("Final Maze:")
        MazeRow=""
        for i in range(0,len(Maze)):
            for j in range(0,len(Maze[i])):
                MazeRow+=str(bin(int(Maze[i][j].CellWalls)))+" "
            print(MazeRow)
            MazeRow=""
    ############################################################################
    #Set Starting Cell
    AppendCell(CellStart)
    #Main loop of the algorithm generating the maze.
    while CellsConsumed < CellsTotal and len(CellStack)>0:
        #Find Non-visited neighbors of current cell
        CellNeighbors = GetNeighbors(CellStart)
        if len(CellNeighbors)>0:
            #choose random neighbor
            NeighborChoice=CellNeighbors[random.randrange(0,len(CellNeighbors))]
            #Set walls of current Cell
            SetWalls(NeighborChoice[0],NeighborChoice[1])
            #Set coordinates of neighbor
            CellNeighbor=[CellStack[-1][0]+NeighborChoice[0],CellStack[-1][1]+NeighborChoice[1]]
            #Call Helper Function: Set to Visited, push current cell coord, increment cellsconsumed
            AppendCell(CellNeighbor)
            CellsConsumed += 1
        else:
            CellStack.pop()
    #Main while loop done
    PrintMaze()
    return
